#pragma once

#include <vector>
using std::vector;

#include <utility>
using std::swap;


template <class T>
class min_heap
{
public:
    // 初始化一个空堆
    min_heap()
        : m_array(nullptr)
        , m_size(0)
        , m_capacity(0)
    {
        
    }

    // 利用一串已知序列, 初始化小根堆
    min_heap(const vector<T>& v)
    {
        m_size = v.size();
        m_capacity = m_size;
        m_array = new T[m_size];
        for (int i = 0; i < m_size; ++i)
        {
            m_array[i] = v[i];
        }

        // 建小堆
        for (int root = (m_size-1-1)/2; root >= 0; --root)
        {
            //T cur = m_array[root];
            int cur_pos = root;
            int min_child_pos = cur_pos * 2 + 1;
            while (min_child_pos < m_size)
            {
                if (min_child_pos+1 < m_size && m_array[min_child_pos] > m_array[min_child_pos+1])
                {
                    ++min_child_pos;
                }

                if (m_array[min_child_pos] >= m_array[cur_pos])
                {
                    break;
                }
                else 
                {
                    swap(m_array[cur_pos], m_array[min_child_pos]);
                    cur_pos = min_child_pos;
                    min_child_pos = 2 * cur_pos + 1;
                }
            }
            
        }

    }

    ~min_heap()
    {
        delete[] m_array;
        m_array = nullptr;
        m_size = 0;
        m_capacity = 0;
    }

    void reserve(int new_capacity)
    {
        if (new_capacity > m_capacity)
        {
            T* tmp = new T[new_capacity];
            for (int i = 0; i < m_size; ++i)
            {
                swap(tmp[i], m_array[i]);
            }

            delete[] m_array;
            m_array = tmp;
            m_capacity = new_capacity;
        }
    }

    void push(const T& x)
    {
        if (m_size == m_capacity)
        {
            int new_capacity = m_capacity == 0 ? 4 : 2 * m_capacity;
            reserve(new_capacity);
        }

        m_array[m_size] = x;
        ++m_size;

        int cur_pos = m_size - 1;
        int parent_pos = (cur_pos - 1) / 2;
        while (cur_pos > 0)
        {
            if (m_array[parent_pos] > m_array[cur_pos])
            {
                swap(m_array[parent_pos], m_array[cur_pos]);
                cur_pos = parent_pos;
                parent_pos = (cur_pos - 1) / 2;
            }
            else
            {
                break;
            }
        }
    }

    void pop()
    {
        if (m_size == 0)
        {
            return;
        }

        //m_array[0].~T(); // 这一行代码会导致错误, 但是为什么???
        //T cur = m_array[m_size - 1];
        swap(m_array[m_size - 1], m_array[0]);
        //m_array[m_size - 1].~T();
        --m_size;

        int cur_pos = 0;
        int min_child_pos = 2 * cur_pos + 1;
        // 这个循环终止, 要么是到叶子了, 要么位置合适了. 判断位置
        while (min_child_pos < m_size)
        {
            if (min_child_pos + 1 < m_size && m_array[min_child_pos] > m_array[min_child_pos+1])
            {
                ++min_child_pos;
            }

            if (m_array[min_child_pos] > m_array[cur_pos])
            {
                break;
            }
            else
            {
                swap(m_array[cur_pos], m_array[min_child_pos]);
                cur_pos = min_child_pos;
                min_child_pos = 2 * cur_pos + 1;
            }
        }
    }

    T& top()
    {
        return m_array[0];
    }

    int size()
    {
        return m_size;
    }

    bool empty()
    {
        return m_size == 0;
    }

private:
    T* m_array;
    int m_size;
    int m_capacity;
};